pub fn dp_rec_mc(amount: u32) -> u32 {
    if(amount < 1){
        return 0;
    }
    // 拿到剩余的钱数
    let mut remaining = find_min(amount);
    let mut number = 1;
    while remaining.1 > 0{
        // 找零次数
        number += 1;
        // 拿到剩余的钱数
        remaining = find_min(remaining.1);
    }
    number
}

/**
    找到纸币中应该给他最大的那个钱数，然后返回还要找个他的钱数
    因为需要尽可能的少找钱，所以每次找的应该都是尽可能大的
*/
pub fn find_min(money:u32) -> (u32, u32){
    // 目前有的现金金额
    let moneys = [1 , 2, 5, 10, 20, 30, 50, 100, 200];
    // 需要找钱的下标
    let index = 0;
    // 遍历现金数组
    for i in 0..moneys.len(){
        // 找到哪一个金额比需要找零的金额大（非等于）
        if(money < moneys[i] as u32){
            if i==0{
                // 没有，就返回0
                return (0,0);
            }else{
                // 有，就返回前一个金额以及还需要找零多少钱
                return (moneys[i - 1], money - moneys[i - 1]);
            }
        }
    }
    (0,0)
}
